package me.timlong.StringDynamic;

public class PanlindromePartition {

    /**
     * 题目描述：
     *
     * 给出一个字符串s，分割s使得分割出的每一个子串都是回文串
     * 计算将字符串s分割成回文分割结果的最小切割数
     * 例如:给定字符串s="aab",
     * 返回1，因为回文分割结果["aa","b"]是切割一次生成的。
     *
     * 解决方案：
     * s="aab"
     * f(i, j) -> s(i, j) 的最小切点数
     * s(i, j) 是回文字符串，则f(i, j) = 0
     *
     * 切割： f(i, j) = f(i, p) + f(p + 1, j) + 1
     *
     * 最终的返回结果为 f(0, s.len)
     *
     *
     */
    public int minCut(String s) {
        int strLen = s.length();
        int i = 0;
        int j = strLen - 1;

        int[][] dp = new int[strLen][strLen];

        for (int k = 0; k < strLen; k++)
            for (i = 0, j = k; j < strLen; i++, j++)
                dpCalculate(s, i, j, dp);

        return dp[0][strLen - 1];

    }

    private int dpCalculate(String str, int i, int j, int[][] dp) {
        int minCutTmp = Integer.MAX_VALUE;
        if(isPanlindrome(str.substring(i, j + 1)))
            dp[i][j] = 0;
        else {
            for (int p = i; p < j; p++)
                minCutTmp = Math.min(dp[i][p] + dp[p + 1][j] + 1, minCutTmp);

            dp[i][j] = minCutTmp;
        }
        return dp[i][j];
    }


    public static void main(String[] args) {
        String s = "baasdfkaflkaemsdab";

        System.out.println(new PanlindromePartition().minCut(s));

    }

    private boolean isPanlindrome(String str){
        int strLen = str.length();

        int i = 0;
        int j = strLen - 1;
        while(i < j){
            if(str.charAt(i) != str.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }

}
